总结一下套路：
1.二分图
二分图对偶定理：
二分图最大权匹配 二分图最小点权覆盖 二分图最大点权独立集
1.最小点权覆盖
将二分图的两部分分别与源点/汇点连容量为点权的边，二分图内部的边容量设为
最后图的最小割即为原二分图的最小点权覆盖。
考虑这样做的正确性：
二分图的点覆盖中每条边都至少被一个点覆盖，所以没有源点到汇点的路径，是新图的割。
新图的割的边集只可能包含源点与汇点为顶点的边（内部的边容量为 ），那么割掉一条边对应选出这个点。
2.最大点权独立集
由对偶定理和 1. 易得解法，不再赘述。
2.集合划分问题
将元素划分为两个集合 , 满足 且 。
划分的代价为：
同时给定一些关系，若元素 不在同一集合则会有 的代价。
求划分的最小代价。
将一个元素拆成两个点，分别表示选入 集合。再从源点/汇点向两部分的点连容量为 的边（注意容量是反的）。
元素之间的代价可视为 之间连容量为 的边。
当然，为了使 被至少被一个集合选中，在 之间连容量为 的边。
图的最小割即为最小代价。
正确性？
因为 之间的边容量为 ， 不可能是原图的边割集。
所以 之中一定有一点与源汇的边被割去，若 被割则表示选入 集合，反之若 被割则选入 集合。这也解释了建图时容量是相反的。
被割则表示接受 的代价，显然
条边只会被割 条。
可以看出，图的割便是一个选择方案，选择方案也对应一个割。求出最小割即可。
P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查
3.方格问题
- 格子之间有要求
格点之间的要求视作边，若是二分图则是最大点权独立集。
- 每行、每列、每个格子有要求
对于每行、每列分别建一个点
行与列之间的边对应格子限制，源点与行的边 / 汇点与列的边 对应 行 / 列 的限制。
值得注意的是，这个图也是一个二分图。
4.最大权闭合子图
5.最大密度子图
2020.12.18 拆点、最大流
P3153 [CQOI2009]跳舞
二分答案 + 拆点 + 最大流
P3163 [CQOI2014]危桥
最大流
2020.12.19 最大流/最小割
SP839 Optimal Marks
按位考虑 + 最小割
2020.12.21 上下界网络流
P4311 士兵占领
P4843 清理雪道
UVA1440 Inspection
2020.12.22 上下界网络流
P4194 矩阵
2020.12.23 拆点、最大流
UVA12125 March of the Penguins
拆点
SP4063 Sell Pigs
最大流建模
2020.12.24 最大流/最小割
P1344 [USACO4.4]Pollutant Control
特殊处理：
在最小割最小的前提下，让割的边最少。
对每一条 的边变为 。
最后 为最小割， 为最少边。
P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查
最小割建模
2020.12.25 最小割
UVA1660 Cable TV Network & SP300 Cable TV Network
最小割建模
P4662 [BalticOI 2008]黑手党
最小割建模
P3191 [HNOI2007]紧急疏散
最大流建模
